Corelab Seminar
2009-2010
Manos Thanos (NTUA)
Online primal-dual algorithms for covering and packing problems
Abstract. The primal-dual schema is a powerful technique that has been used extensively to obtain algorithms for many important problems. This technique, which used to be common for the design of offline algorithms, has been applied also to online problems such as covering and packing optimization problems. In an online covering problem a linear cost function is known in advance, but the linear constraints that define the feasible solution space are given one by one in an online fashion. In an online packing problem the profit function as well as the exact packing constraints are not fully known in advance. In each round additional information about the profit function and the constraints is revealed. The scheme discussed, is designed via a novel primal-dual technique that extends the scheme used for many offline optimization problems. Recently, it was shown that this general primal-dual framework is useful for capturing many more online problems, a fact that aggrandizes the importance of this scheme.